The present invention relates generally to content addressable memories (CAMs) and more particularly to CAMs having configurable options.
Information networks, including the Internet, can operate under various networking protocols. Data packets within a network can be processed according to a protocol xe2x80x9cstackxe2x80x9d having different layers. A data packet will typically include a header with various fields corresponding to various layers of a protocol stack.
Network hardware for processing data packets, such as a router or network switch, can include tables that store data corresponding to various network layers. When a packet arrives to a router and/or network switch, one or more fields in the packet header can be compared to corresponding tables. The packet can then be processed according to the comparison results. Content addressable memories (CAMs), also referred to as xe2x80x9cassociative memories,xe2x80x9d can provide rapid matching functions often needed in routers and network switches.
A complicating factor in packet processing can be the variable length of the various fields in a protocol stack. Such variable length fields can result in routers or network switches having a CAM dedicated to each particular field length. Consequently, when multiple fields are processed, multiple CAM devices are utilized. This can increase the size and/or cost of the resulting network hardware.
A typical CAM can store a number of data values in a CAM cell array. In a compare (i.e., match) operation, the data values can be compared to a comparand value (also referred to as a xe2x80x9csearch keyxe2x80x9d). A data value that matches the comparand value can result in a match indication. Match indications can be prioritized by a priority encoder and be utilized to generate associated data. One example of associated data can be xe2x80x9cnext hopxe2x80x9d information in the case of a connectionless network structure.
CAMs can be synchronous and/or asynchronous. A synchronous CAM can perform matching functions on applied comparand values according to a periodic timing signal (such as a system clock, as one example). An asynchronous CAM can perform matching functions on applied comparand value according a non-periodic timing signal (such as an applied comparand value, as just one example).
It is often desirable for synchronous CAMs to operate according to particular timing specifications. As just one example, it is desirable to have a CAM that can receive a comparand value on a certain clock edge, and then provide a compare result a predetermined number of clock cycles later. Such configurations can allow data values to be xe2x80x9cpipelined,xe2x80x9d which can generate compare results every clock cycle.
CAMs can include xe2x80x9cbinaryxe2x80x9d CAMs in which a multi-bit comparand value must match with every bit of a data value to generate a match indication. CAMs can also include xe2x80x9cternaryxe2x80x9d CAMs in which multi-bit comparand values can be compared with xe2x80x9cmaskablexe2x80x9d data values. A maskable data value can have one or more bits that can be masked from the compare operation. A masked data value bit will not generate a mismatch indication even if the masked data value bit is different than the corresponding comparand value bit.
A conventional CAM will now be described to better understand the various disclosed embodiments of the present invention.
Referring now to FIG. 9, a block diagram is set forth illustrating a conventional CAM. The conventional CAM is designated by the general reference character 900, and is shown to include CAM cell array 902, a comparand register 904 and a priority encoder 906. A CAM cell array 902 can include a number of entries, shown as xe2x80x9cENTRY mxe2x80x9d through xe2x80x9cENTRY 0.xe2x80x9d Each entry can store a data value that is compared to an applied comparand value. Further, each entry has the same number of bits. In the arrangement of FIG. 9, each entry can include xe2x80x9cn+1xe2x80x9d bits. In many CAMs an entry corresponds to a row of CAM cells.
One way to conceptualize a CAM cell array 902 is to describe it as having a particular width and depth. A width can be the size of the data values stored and a depth can be the total number of data values that can be stored. Accordingly, in the example of FIG. 9, the CAM cell array 902 has a depth of m+1 and a width of n+1.
A comparand register 904 can store a comparand value that is to be compared with data values in the CAM cell array 902. In the arrangement of FIG. 9, a comparand will typically have the same width as the CAM cell array 902.
A CAM cell array 902 can receive a comparand value by way of compare lines 908. Resulting match results (which may be a xe2x80x9cmatchxe2x80x9d or xe2x80x9cno match,xe2x80x9d for example) can be provided by way of match lines 910. Typically, one match line can be associated with each entry of the CAM cell array 902.
The priority encoder 906 can encode match indications into corresponding index values INDEX. Further, if more than one of the match lines 910 indicates a match, a priority encoder 906 can generate one INDEX value according to predetermined criteria (such as entry position, as but one example).
Referring now to FIG. 10, a typical ternary CAM array row is illustrated in a schematic diagram. The CAM array row is designated by the general reference character 1000, and is shown to include xe2x80x9cn+1xe2x80x9d ternary CAM cells 1002(m,n) to 1002(m,0). The ternary CAM cells (1002(m,n) to 1002(m,0)) of the row are commonly connected to a match line 1004. Each ternary CAM cell (1002(m,n) to 1002(m,0) is further connected to a corresponding comparand line (1006-n to 1006-0).
Each ternary CAM cell (1002(m,n) to 1002(m,0) includes a data store 1008, a mask store 1010, and a maskable compare circuit 1012. A data store 1008 can store a data value portion (such as a bit). A mask store 1010 can store a mask value portion (such as a bit). A maskable compare circuit 1012 can compare a data value portion to a comparand portion on a compare line. The results of the compare operation can be masked (or not masked) according to a mask value portion.
In one particular arrangement, a match line 1004 can be precharged (or predischarged) to a particular potential, and then be discharged (or charged) when one or more CAM cells (1002(m,n) to 1002(m,0) indicates a mismatch (i.e., no match between a comparand portion and stored data value portion).
A ternary CAM can advantageously provide specialized match functions, such as a longest prefix match. A longest prefix match can provide a match indication for a data value having the largest number of leading consecutive bits that match a comparand value. Longest prefix matching can be a valuable function in many types of network hardware.
To provide a match function for multiple layer fields, multiple CAMs, such as that set forth in FIG. 9 can be used, with one or more CAMs being dedicated to a particular field length.
It would be desirable arrive at some way of providing match functions for multiple fields that includes fewer system components.
According to the disclosed embodiments, a content addressable memory (CAM) can include a number of CAM cells formed in an array and arranged into two or more sections. Each section can have an independently configurable width.
According to one aspect of the embodiments, a CAM can include a number of entries that each provide an entry match indication that can provide match results between comparand and data values of a first size. Multiple entry match indications can be combined to provide match indications between comparand and data values of a second size that is larger than the first size.
According to another aspect of the embodiments, a CAM can include two or more sections having independently configurable widths and a configuration register. The sections can be configured according to configuration information stored in the configuration register.
According to another aspect of the embodiments, a CAM can include two or more sections, each having at least two sub-sections. Each section can be configured into a first, second, or third mode. In a first mode, a comparand can be compared to the two sub-sections of a section. In a second mode, a first comparand value portion can be compared to one sub-section and a second comparand value portion can be compared to another section. In a third mode, a first comparand value portion can be compared to selected entries in a first sub-section, a second comparand value portion can be compared to selected entries in a second sub-section, a third comparand value portion can be compared to selected entries in the first sub-section, and a fourth comparand value portion can be compared to selected entries in the second sub-section.
According to another aspect of the embodiments, a CAM can include a first mode that compares a comparand value to data values in a single compare operation to generate match results. The CAM can further include a second mode that compares a comparand value to data values with multiple compare operations. Match indications from the multiple compare operations can be logically combined to generate match results.
According to another aspect of the embodiments, a CAM can include two or more sections of ternary CAM cells that have independently configurable widths.